class Solution {
public:
    int totalFruit(vector<int>& f) {
       // 准备， 通过hash和 kinds 对水果类型进行判断
       int hsh[100001];
       int size = f.size();
       int ret = 0;
       for(int left = 0, right = 0, kinds = 0; right < size; right++)
        {
            if(hsh[f[right]] == 0) kinds++;
            hsh[f[right]]++;     
            while(kinds > 2)
            {
                hsh[f[left]]--;
                if(hsh[f[left]] == 0) kinds--;
                left++;
            }
            ret = max(ret, right - left + 1);
        }
        return ret;
        
        // 入窗口
        // 判断结果
        // 出窗口
        // 更新结果
        // 
    }
};




class Solution {
public:
    bool check(int hash1[], int hash2[])
    {
        for(int i = 0; i < 26; i++)
        {
            if(hash1[i] != hash2[i]) return false;
        }
        return true;
    }

    vector<int> findAnagrams(string s, string p) {
        // 解法1
        int hash1[26], hash2[26];
        int size = s.size();
        int lenp = p.size();
    
        for(auto c : p) hash2[c - 'a']++;
        vector<int> ret;
        for(int left = 0, right = 0; right < size; right++)
        {
            hash1[s[right] - 'a']++;
            if(right - left + 1 > lenp)
            {
                hash1[s[left] - 'a']--;
                left++;
            }
            if(check(hash1, hash2))
                ret.push_back(left);
        }
        return ret;
    }
};
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        // 解法2：不适用check判断，使用count计数器来统计有效字符
        int hash1[26] = { 0 };
        for(auto c : p) hash1[c - 'a']++;

        int hash2[26] = { 0 };
        vector<int> ret;
        int m = p.size();
        for(int left = 0, right = 0, count = 0; right < s.size(); right++)
        {
            // 进窗口
            //hash2[s[right] - 'a']++;
            if(++hash2[s[right] - 'a'] <= hash1[s[right] - 'a']) count++;
            if(right - left + 1 > m) 
            {
                if(hash2[s[left] - 'a']-- <= hash1[s[left] - 'a']) count--;
                //hash2[s[left] - 'a']--;
                left++;
            }
            if(count == m) ret.push_back(left);
        }
        return ret;
    }
};